package it.storm.solution;

/**
 * 面试题 16.10. 生存人数
 * https://leetcode-cn.com/problems/living-people-lcci/
 */
public class Solutions_mianshi_16_10 {
    public static void main(String[] args) {
        int[] birth = {1900, 1901, 1950};
        int[] death = {1948, 1951, 2000};  // output: 1901

        int result = maxAliveYear(birth, death);
        System.out.println(result);
    }

    /**
     * 解法一：线性扫描（2ms）
     * 解题思路：通过绘制一条坐标轴模拟某年份的出生、死亡人数，即可得到该解法
     */
    public static int maxAliveYear(int[] birth, int[] death) {
        // 为什么 102？因为若 1951 dead，那么 1951 时，此人而是 live 状态
        // 只有到了 1951 + 1 = 1952 时，此人才不计入生存人数中
        // counts[1] = 2：表示 1900 + 1 = 1901 年，生存人数为 2
        int[] counts = new int[102];
        int res = 0, maxCount = 0;
        for (int i = 0; i < birth.length; i++) {
            counts[birth[i] - 1900] ++;
            // 为什么加 1？因为 death[i] 年 dead 后，只有在 death[i] + 1 年，此人才不计入生存人数中
            counts[death[i] - 1900 + 1] --;
        }

        int liveCnt = 0;
        for (int i = 0; i < counts.length; i++) {
            // 积累起来，则可以计算出 i + 1900 年时，生存人数的数量
            liveCnt += counts[i];
            if (liveCnt > maxCount) {
                // 因为是从前往后遍历，那么有多个年份生存人数相同且均为最大值时，res 一定是最小的年份
                res = i + 1900;
                maxCount = liveCnt;
            }
        }
        return res;
    }

    /**
     * 解法二：暴力法（6ms）
     */
    public static int maxAliveYear2(int[] birth, int[] death) {
        // counts[1] = 2：表示 1900 + 1 = 1901 年的生存人数为 2
        int[] counts = new int[101];
        for (int i = 0; i < birth.length; i++) {
            int j = birth[i] - 1900, k = death[i] - 1900;
            while (j <= k) {
                // [j, k] 年的生存人数都加 1
                counts[j] ++;
                j++;
            }
        }
        // counts 中找到第一次出现的最大值
        int res = 0, maxCnt = 0;
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] > maxCnt) {
                res = 1900 + i;
                maxCnt = counts[i];
            }
        }
        return res;
    }
}
